package everyday.leetcode.editor.cn;

import com.dq.utils.CreateArray;
import lombok.Data;
import lombok.extern.log4j.Log4j;
import lombok.extern.slf4j.Slf4j;

import java.util.LinkedList;

/**
 * @ClassName: PathWithMinimumEffort
 * @Author: Dang Qi
 * @Date: 2021/1/29  14:09
 * @Question.Title: 最小体力消耗路径
 * @Question.No: 1631
 */
public class PathWithMinimumEffort {
    int a = 0;
    public static void main(String[] args) {
        Solution solution = new PathWithMinimumEffort().new Solution();
        String s = "[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]";
        int[][] heights =(int[][])CreateArray.genIntArray(s);
        int res = solution.minimumEffortPath(heights);

        System.out.println(res);

    }
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution2{
        public int minimumEffortPath(int[][] heights) {
            return 0;
        }

    }



    class Solution {
        public int minimumEffortPath(int[][] heights) {
            return dijkstra(heights);
        }
        public int dijkstra(int[][] heights){
            boolean[][] visit = new boolean[heights.length][heights[0].length];
            int[] min = new int[3];
            int[][] dist = new int[heights.length][heights[0].length];
            //初始化distance数组
            for (int i = 0; i < dist.length; i++) {
                for (int j = 0; j < dist[0].length; j++) {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
            dist[0][0] = 0;

            int vi = 0, vj = 0;
            while (vi!=heights.length-1 || vj!=heights[0].length-1){
                findMin(dist,visit,min);
                vi = min[1];
                vj = min[2];
                //将当前节点加入到S集合
                visit[vi][vj] = true;
//                System.out.printf("(%d,%d)\n", vi, vj);
                //遍历结点[vi,vj]的邻边及节点
                // 进行松弛操作
                travelNeighbor(vi,vj,vi-1,vj, dist,heights,visit,min);
                travelNeighbor(vi,vj,vi+1,vj, dist,heights,visit,min);
                travelNeighbor(vi,vj,vi,vj-1, dist,heights,visit,min);
                travelNeighbor(vi,vj,vi,vj+1, dist,heights,visit,min);
            };

            return dist[heights.length-1][heights[0].length-1];
        }
        public void travelNeighbor(int i, int j, int nextI, int nextJ, int[][] dist, int[][] height,boolean[][] visit, int[] min){
            //超出边界，直接返回
            if(nextI<0 || nextI==height.length || nextJ<0||nextJ==height[0].length) return;
            //如果已经加入到S集合中时，直接返回
            if(visit[nextI][nextJ]) return;
            //边的大小
            int edge = edgeLen(i,j,nextI,nextJ,height);
            //如果说下一个节点的绝对值大小大于上一个，则更新为edge,否则为上一个
            int distance = edge>dist[i][j]?edge:dist[i][j];
            //如果小于之前的distance的话
            if(distance<dist[nextI][nextJ]){
                dist[nextI][nextJ] = distance;
            }

        }
        public int edgeLen(int i, int j, int ni, int nj, int[][] heights){
            int res = heights[i][j] - heights[ni][nj];
            return res>=0?res:-res;
        }
        public void findMin(int[][] dist, boolean[][] visit, int[] min){
            min[0] = Integer.MAX_VALUE;
            for (int i = 0; i < dist.length; i++) {
                for (int j = 0; j < dist[i].length; j++) {
                    if(!visit[i][j] && dist[i][j]<min[0]){
                        min[0] = dist[i][j];
                        min[1] = i;
                        min[2] = j;
                    }
                }
            }
        }
    }


    //leetcode submit region end(Prohibit modification and deletion)
}
